package two.chapter_1.c1_5;

import edu.princeton.cs.algs4.StdOut;

public class QuickFindUF extends UF {


    public QuickFindUF(int N) {
        super(N);
    }

    /**
     *  数组访问次数  最好的情况（只需更改一个点）  1+1+N+1  =N+3
     *              最坏的情况（需要更改N-1个点） 1+1+N +N-1  =2N+1
     *
     *  假设N个结点最后只得到一个连通分量，那么这至少需要调用N-1次union()，即至少（N+3)(N-1) ~N^2 次数组访问
     * @param p
     * @param q
     */
    @Override
    public void union(int p, int q) {
        int accessCount=0;
        int pId = find(p);
        accessCount++;
        int qId = find(q);
        accessCount++;
        if (pId != qId) {
            for (int i = 0; i < ids.length; i++) {
                accessCount++;
                if (ids[i] == pId) {
                    accessCount++;
                    ids[i] = qId;
                }
            }
            count--;
        }
        StdOut.println("accessCount:"+accessCount);
    }

    @Override
    public int find(int p) {
        while (ids[p] != p) {   //最坏情况// N次
            p = ids[p];//N-1次
            ids[p]=p;//直接指向根结点P
        }
        return p;
    }
}
